package leetcode_100;

/**
 *@author 周杨
 *RegularExpressionMatching_10_ 表达式匹配 *可以复制前一个符号0次至无限次 .能匹配任意一个字符
 *describe:用动态规划 dp[i][j]表示两个字符串在i和j下标使的匹配状态 AC 99%
 *2018年12月19日 下午5:04:05
 */
public class RegularExpressionMatching_10_ {
	 public static void main(String[] args) {
		 RegularExpressionMatching_10_ test=new RegularExpressionMatching_10_();
		 System.out.println(test.isMatch("a", "aa"));
		 System.out.println(test.isMatch("aa", "a*"));
		 System.out.println(test.isMatch("ab", ".*"));
		 System.out.println(test.isMatch("aab", "c*a*b"));
		 System.out.println(test.isMatch("mississippi", "mis*is*p*."));
		 System.out.println(test.isMatch("", "c*c*"));
	}
	
	 public boolean isMatch(String s, String p) {
		 if(s==null||p==null) return false;
		 boolean [][]dp=new boolean[s.length()+1][p.length()+1];
		 //dp[i][j]表示第s中第i个字符和p中第j个字符匹配
		 dp[0][0]=true;
		 char []chars1=s.toCharArray();
		 char []chars2=p.toCharArray();
		 //不考虑**的情况
		 for(int i=1;i<chars2.length;++i) {
			 if(chars2[i]=='*'&&dp[0][i-1]) {
				 dp[0][i+1]=true;
			 }
		 }
		 for(int i=0;i<chars1.length;++i) {
			 for(int j=0;j<chars2.length;++j) {
				 if(chars2[j]=='.'||chars2[j]==chars1[i]) {
					 dp[i+1][j+1]=dp[i][j];
				 }
				 else if(chars2[j]=='*') {
					 if(chars2[j-1]!=chars1[i]&&chars2[j-1]!='.') {
						 //*之前的字符匹配不上 
						 dp[i+1][j+1]=dp[i+1][j-1];
					 }
					 else {
						 dp[i+1][j+1]=(dp[i+1][j]||dp[i][j+1]||dp[i+1][j-1]);
					 }
				 }
			 }
		 }
		 return dp[chars1.length][chars2.length];
	 }
}
